﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
//读完题，注意题目中的陷阱
//"catsandog", wordDict = ["cats", "dog", "sand", "and", "cat"]
//可能是sand+og，也可能是san+dog，或者s+and+og,所有不可以使用贪心
public class Solution139
{
    public bool WordBreak2(string s, IList<string> wordDict)//尝试使用递归法失败，动态规划还是不要使用递归
    {

        //不需要求最少的
        //dp[i]=dp[s-word]
     
        if(s.Length == 0) return true;



        for (int j = 0; j < wordDict.Count; j++)
        {
          string  news = s.Replace(wordDict[j], "");//s里面没有wordDict[j]会报错吗,不会报错，但是也不替换

            if (news == s)
            {
                return false;//说明没有可以拆分的单词
            }
            else
            {
              return  WordBreak(s, wordDict);//有一个true就行
            }
         
        }

        //string    a = "lat";

        //s = s.Replace(a, "");
        //Console.WriteLine(s);


        return true;

    }
    public bool WordBreak(string s, IList<string> wordDict)//尝试使用迭代动态规划
    {

        //不需要求最少的
        //dp[i]=dp[s-word]}
        //Dictionary<string,string> dict = new Dictionary<string,string>(wordDict);//字典不行不行
        HashSet<string> words = new HashSet<string>(wordDict);


        bool[] dp= new bool[s.Length+1];//默认使用false初始化
        dp[0]= true;
        //for(int i = 1; i <= s.Length; i++)
        //{
        //    Console.WriteLine(dp[i]);
        //}

        for (int i =1 ; i <= s.Length; i++)
        {
            for (int j = 0; j < i; j++)//j的作用不是遍历wordDict，而是遍历所有i-j之间的单词(也就是检查word）是否符合要求（在wordDict里面）
            {//dp[i]=dp[s-word]}
                //word符合要求，那么dp[i]就转移到dp[j]的状态
                //有bug
                //if (words.Contains(s.Substring(j, i - j))){

                //    dp[i] = dp[j];//d[j]false不符合的会导致dp【i】也为false，dp[i]在这个循环里面一直变化，导致dp[i]=dp[j-1]
                //}
                if (dp[j]&&words.Contains(s.Substring(j, i - j)))
                {

                    dp[i] =true ;
                    break;//意思是只有一种情况符合，提前终止
                }

            }
        }
        return dp[s.Length];
    }
   
    }
    class Program139
{

    static void Main139(string[] args)
    {

        Solution139 solution = new Solution139();
        //string s = "leetcode";
        string s = "aaaaaaa";
        //IList<string> wordDict = ["leet", "code"];
        IList<string> wordDict = ["aaaa", "aaa"];

      bool res=  solution.WordBreak(s,wordDict);
        Console.WriteLine(res);

    }
}
